/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
	ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
		if (!pHead1 && !pHead2)
			return nullptr;
		else if (pHead1 && !pHead2)
			return pHead1;
		else if (!pHead1 && pHead2)
			return pHead2;
		ListNode* min = pHead1;
		ListNode* max = pHead2;
		if (pHead1->val > pHead2->val)
		{
			min = pHead2;
			max = pHead1;
		}
		ListNode* ret = min;
		while (min->next && max)
		{
			ListNode* cur = max->next;
			if (min->next->val >= max->val)
			{
				max->next = min->next;
				min->next = max;
				min = max;
				max = cur;
			}
			else
				min = min->next;
		}
		if (max)
			min->next = max;
		return ret;
	}
};